package org.leetcode.middle.leetcode22;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution {

    List<String> res = new ArrayList<>();

    StringBuilder str = new StringBuilder();

    public List<String> generateParenthesis(int n) {

        backtracking(0,0,n);
        return res;
    }


    private void backtracking(int left,int right,int n){
        if (str.length()==2*n) {
            res.add(str.toString());
            return;
        }
        if (left<n){
            str.append("(");
            backtracking(left+1,right,n);
            str.deleteCharAt(str.length()-1);
        }

        if (left>right){
            str.append(")");
            backtracking(left,right+1,n);
            str.deleteCharAt(str.length()-1);
        }
    }

//    private boolean isValid(StringBuilder str){
//        return true;
//    }

}
